package ink.lovejinhu.leetcode;

import ink.lovejinhu.common.ListNode;

import java.util.Stack;

/**
 * @author jinhu
 * created 2021-07-02 9:04
 */
public class Solution_0160
        /**
         * 两个链表的交点
         */
{
    /**
     * 这是最简洁的做法
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == null || headB == null) return null;
        /**
         * 官方解答，相当于PA走了链表A+链表B-公共的部分距离
         *            PB而是先走链表B+链表A-公共部分距离
         */
        ListNode pA = headA, pB = headB;

        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;

    }

    /**
     * 用两个栈
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode01(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        Stack<ListNode> listNodeOfA = new Stack<>();
        Stack<ListNode> listNodeOfB = new Stack<>();
        while (headA != null) {  //入栈

            listNodeOfA.push(headA);
            headA = headA.next;
        }
        while (headB != null) {   //入栈

            listNodeOfB.push(headB);
            headB = headB.next;
        }
        ListNode res = null;
        while ((!listNodeOfA.isEmpty()) && (!listNodeOfB.isEmpty())) {
            if (listNodeOfA.peek() == listNodeOfB.peek()) {
                res = listNodeOfA.peek();
                listNodeOfA.pop();
                listNodeOfB.pop();
            } else {
                break;
            }

        }
        return res;
    }

}
